#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000;
const int maxm=2000000;
int n;
int Arr[maxn+5];
struct SegmentTree{
    long long mx[4*maxm+5];
    long long tag[4*maxm+5];
    void pushdown(int p){
        if(tag[p]){
            mx[p<<1]+=tag[p];
            tag[p<<1]+=tag[p];
            mx[p<<1|1]+=tag[p];
            tag[p<<1|1]+=tag[p];
            tag[p]=0;
        }
    }
    void pushup(int p){
        mx[p]=max(mx[p<<1],mx[p<<1|1]);
    }
    void Build(int L,int R,int p){
        mx[p]=-1e15;
        tag[p]=0;
        if(L==R){
            return;
        }
        int mid=(L+R)>>1;
        Build(L,mid,p<<1);
        Build(mid+1,R,p<<1|1);
    }
    void Modify(int L,int R,int l,int r,long long c,int p){
        if(L==l&&R==r){
            tag[p]+=c;
            mx[p]+=c;
            return;
        }
    }
    void Insert(int L,int R,int pos,long long c,int p){
        if(L==R){
            mx[p]=max(mx[p],c);
            return;
        }
        pushdown(p);
        int mid=(L+R)>>1;
        if(pos<=mid){
            Insert(L,mid,pos,c,p<<1);
        }
        else{
            Insert(mid+1,R,pos,c,p<<1|1);
        }
        pushup(p);
    }
    long long Query(int L,int R,int pos,int p){
        if(L==R){
            return mx[p];
        }
        pushdown(p);
        int mid=(L+R)>>1;
        if(pos<=mid){
            return Query(L,mid,pos,p<<1);
        }
        else{
            return Query(mid+1,R,pos,p<<1|1);
        }
    }
}SGT;
void Solve(){
    scanf("%d",&n);
    SGT.Build(0,maxm,1);
    SGT.Insert(0,maxm,0,0,1);
    for(int i=1;i<=n;i++){
        scanf("%d",&Arr[i]);
        long long temp=max(SGT.mx[1],SGT.Query(0,maxn,Arr[i],1)+Arr[i]);
        if(Arr[i]==Arr[i-1]){
            SGT.Modify(0,maxm,0,maxm,Arr[i],1);
        }
        SGT.Insert(0,maxn,Arr[i-1],temp,1);
    }
    printf("%lld\n",SGT.mx[1]);
}
signed main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        Solve();
    }
    return 0;
}